#include <string>
#include <iostream>

using namespace std;


template <typename T>
struct Node
{
    T data; // 数据域
    Node<T>* next; // 指针域
};


template <typename T>
class LinkList
{
public:
    LinkList();
    ~LinkList()=default;
public:
    bool insert(int i,const T& e); // 插入
    bool del(int i); // 删除
    bool get(int i,T& e); // 获取
    int indexOf(const T& e); // 查找
    void print(); // 打印
    int len();// 长度
    bool isEmpty();// 判空
    void reverse();// 反转
private:
    Node<T>* m_head; // 头节点
    int m_length;
};



template <typename T>
LinkList<T>::LinkList() 
{
    m_head = new Node<T>;
    m_head->next = nullptr;
    m_length = 0;
}

// template <typename T>
// LinkList<T>::~LinkList()
// {
//     Node<T>* p = m_head;
//     while (p!= nullptr)
//     {
//         Node<T>* q = p->next;
//         delete p;
//         p = q;
//     }
// }



template <typename T>
bool LinkList<T>::insert(int i,const T& e)
{
    if (i<0 || i>m_length)
    {
        cout << "插入位置不合法" << endl;
        return false;
    }
    Node<T>* p = m_head;
    for (int j = 0; j < i - 1; j++)
    {
        p = p->next;
    }
    Node<T>* s = new Node<T>;
    s->data = e;        
    s->next = p->next;
    p->next = s;
    cout << "插入成功" << endl;
    m_length++;
    return true;
}


template <typename T>
bool LinkList<T>::del(int i)
{
    if (i<0 || i>m_length)
    {
        cout << "删除位置不合法" << endl;
        return false;
    }
    Node<T>* p = m_head;
    for (int j = 0; j < i - 1; j++)
    {
        p = p->next;
    }
    Node<T>* q = p->next;
    p->next = q->next;
    delete q;
    cout << "删除成功" << endl;
    m_length--;
    return true;
}

template <typename T>
bool LinkList<T>::get(int i, T& e)
{
    if(m_length < 1) {
        cout << "链表为空" << endl;
    }
    if(i < 1 || i > m_length)
    {
        cout << "不合法";
        return false;
    }
    Node<T>* p = m_head;
    for(int j = 0;j < i;j++)
    {
        p = p->next;
    }
    e = p->data;
    cout << "获取成功" << i << "位置" << "的元素，值为" << e << endl;
    return true;
}


template <typename T>
int LinkList<T>::indexOf(const T& e)
{
    Node<T>* p = m_head;
    int i = 0;
    while (p->next!= nullptr)
    {
        p = p->next;
        if (p->data == e)
        {
            cout << "元素" << e << "的位置为" << i << endl;
            return i;
        }
        i++;
    }

    cout << "元素" << e << "不存在" << endl;
    return -1;
}


template <typename T>
void LinkList<T>::print()
{
    Node<T>* p = m_head;
    while (p->next!= nullptr)
    {
        p = p->next;
        cout << p->data << " ";
    }
    cout << endl;
}


template <typename T>
int LinkList<T>::len()
{
    return m_length;
}

template <typename T>
bool LinkList<T>::isEmpty()
{
    return m_length == 0;
}



template <typename T>
void LinkList<T>::reverse()
{
    Node<T>* p = m_head->next;
    Node<T>* q = p->next;
    p->next = nullptr;
    while (q!= nullptr)
    {
        Node<T>* r = q->next;
        q->next = p;
        p = q;
        q = r;
    }
    m_head->next = p;   
}

int main()
{
    LinkList<int> ls;

    ls.insert(0, 4);
    ls.insert(1, 8);
    ls.insert(2, 12);

    // ls.del(1);

    int eval = 0;

    ls.get(1, eval);

    ls.indexOf(12);

    ls.print();


    ls.reverse();


    ls.print();






    cout << "Hello World!\n";
}